W1. Алгоритмы, корректность и анализ, асимптотическая нотация

Автор

Nikolai Kudasov

Дата публикации

29 января 2026 г.

1. Краткое содержание

1.1 Что такое алгоритм?

Алгоритм (algorithm) — это чётко определённая вычислительная процедура, которая за конечное время принимает некоторое значение (или набор значений) как вход (input) и производит некоторое значение (или набор значений) как выход (output). Иными словами, алгоритм — это последовательность вычислительных шагов, которые преобразуют вход в выход.

Другой взгляд: алгоритм — инструмент для решения чётко сформулированной вычислительной задачи (computational problem). Формулировка задачи описывает желаемую связь «вход–выход» в общих чертах, а алгоритм задаёт конкретную процедуру, которая эту связь обеспечивает для всех допустимых экземпляров задачи.

1.1.1 Вычислительные задачи

Вычислительная задача (computational problem) задаёт, в общих чертах, желаемую связь между входом и выходом. Несколько классических примеров:

Задача возведения в степень (Exponentiation Problem):
- Вход: числа \(a\) и \(n\).
- Выход: число \(r\) такое, что \(r = a^n\).
Задача факторизации (Prime Factorization Problem):
- Вход: натуральное число \(n > 1\).
- Выход: последовательность чисел \(\langle p_1, \dots, p_k \rangle\), где каждое \(p_i\) простое и \(\prod_{i=1}^k p_i = n\).
Задача поиска (Search Problem):
- Вход: последовательность из \(n\) чисел \(\langle a_1, a_2, \dots, a_n \rangle\) и число \(x\).
- Выход: индекс \(i\) такой, что \(a_i = x\) (если такой индекс существует), либо специальное значение NOT FOUND (иначе).
Задача сортировки (Sorting Problem):
- Вход: последовательность из \(n\) чисел \(\langle a_1, a_2, \dots, a_n \rangle\).
- Выход: перестановка \(\langle a'_1, a'_2, \dots, a'_n \rangle\) входной последовательности такая, что \(a'_1 \le a'_2 \le \dots \le a'_n\).

1.2 Корректность алгоритма

Алгоритм корректен (correct), если для каждого допустимого входа (как определено вычислительной задачей) он:

Завершается (Terminates) за конечное время, и
Выдаёт корректный выход (Produces a correct output) (в смысле вычислительной задачи).

Например, корректный алгоритм поиска для любой конечной входной последовательности \(\langle a_1, \dots, a_n \rangle\) и числа \(x\) должен завершиться за конечное время и вернуть либо индекс \(i\) с \(a_i = x\), либо значение NOT FOUND, если такого индекса нет.

1.2.1 Подходы к доказательству корректности

Есть три основных подхода к тому, чтобы убедиться, что алгоритм корректен:

Тестирование (Testing) — запуск реализации (или ручная трассировка псевдокода) на конкретных примерах. Это может находить ошибки, но в общем случае корректность не доказывает.
Доказательство «на бумаге» (Pen-and-paper proof) — математический аргумент корректности для всех допустимых входов.
Формальная верификация (Formal verification) — проверяемый компьютером proof of correctness с помощью proof assistants (например, Coq, Isabelle). Это самый строгий, но и самый трудоёмкий путь.

1.2.2 Инварианты цикла (Loop Invariants)

Большинство алгоритмов используют циклы (for, while). Чтобы доказать корректность цикла, вводят инвариант цикла (loop invariant) — свойство (обычно выраженное через переменные цикла), которое истинно на каждой итерации.

Удобная картинка: инвариант — это «обещание», которое цикл выполняет сам себе: «сколько бы раз я ни выполнился, это свойство всё ещё верно». Оно остаётся истинным на протяжении всего выполнения, даже когда переменные меняются.

Чтобы доказать инвариант \(P\), нужно показать три вещи:

Инициализация (Initialization): \(P\) выполняется до первой итерации цикла.
- Это база: инвариант истинен в момент старта.
- Аналог базы в математической индукции.
Сохранение (Maintenance): если \(P\) истинен перед итерацией, то он остаётся истинным и после неё.
- Один проход тела цикла сохраняет инвариант.
- Аналог индуктивного шага: если верно для итерации \(i\), то верно для \(i+1\).
- Нужно показать это для любой итерации, не только для частных случаев.
Завершение (Termination): цикл завершается, и в момент завершения \(P\) даёт полезное свойство для доказательства корректности алгоритма.
- Нужно доказать, что цикл не выполняется бесконечно.
- Когда цикл останавливается, инвариант (вместе с условием завершения) должен давать то, что нужно для корректности.

Связь с математической индукцией: инварианты циклов напрямую соотносятся с индукцией:

База (\(n=0\) или \(n=1\)) → Initialization (до первой итерации)
Индуктивный шаг (если верно для \(n\), то верно для \(n+1\)) → Maintenance (если верно перед итерацией, то верно после)
Отличие: у цикла есть условие termination, а индукция доказывает утверждение для всех натуральных чисел.

1.2.3 Пример инварианта цикла: возведение в степень

Рассмотрим алгоритм вычисления \(a^n\):

function exp(a, n)
begin
    k := 0
    b := 1
    while k != n do
    begin
        k := k + 1
        b := b * a
    end
    return b
end

Инвариант цикла: \(b = a^k\).

Доказательство:

Initialization: до первой итерации \(b = 1\) и \(k = 0\). Поскольку \(a^0 = 1\) для любого \(a\), инвариант выполнен.
Maintenance: пусть перед итерацией \(i\) выполнено \(b_i = a^{k_i}\) и \(k_i \ne n\). После итерации \(k_{i+1} = k_i + 1\) и \(b_{i+1} = b_i \cdot a = a^{k_i} \cdot a = a^{k_i + 1} = a^{k_{i+1}}\). Инвариант сохраняется.
Termination: \(k\) стартует меньше \(n\) и каждый раз увеличивается на 1, поэтому цикл завершится не более чем за \(n\) итераций с \(k = n\). Тогда инвариант даёт \(b = a^n\) — это и есть требуемый выход.

1.3 Анализ алгоритмов

Анализ алгоритма (algorithm analysis) отвечает на вопрос: как требования к ресурсам алгоритма растут с ростом размера входных данных?

Обычно измеряют «ресурсы»:

Время выполнения (Execution time) — time complexity
Дополнительную память (Additional memory) — space complexity

«Размер входа» зависит от задачи:

число элементов в коллекции
длина строки
число цифр (или бит) в числе
размерности матрицы и т.д.

1.3.1 Зачем анализировать алгоритмы?

Анализ позволяет:

Систематически сравнивать (compare) разные подходы к одной задаче.
Определять (Determine), укладывается ли алгоритм в ограничения по ресурсам.
Находить возможности для ускорения (optimization opportunities).

Критически важно: всё это можно сделать до больших затрат времени и денег на полноценную реализацию.

1.3.2 Эмпирический и теоретический анализ

Есть два основных подхода:

Эмпирический подход:

Реализовать алгоритм.
Запускать на входах разного размера (и формы).
Измерять время работы.
Строить графики и подбирать аппроксимирующую кривую.

Практично, но результат зависит от железа, языка, выбранных входов и может не отражать worst-case.

Теоретический (аналитический) подход:

Описать алгоритм псевдокодом (pseudocode) (высокоуровневое описание без деталей реализации).
Оценить время работы как функцию \(T(n)\) от размера входа \(n\).

Даёт результаты, не зависящие от конкретного железа, и часто выявляет истинный асимптотический порядок роста.

Что такое псевдокод? Это упрощённый язык, фиксирующий логику алгоритма без синтаксических деталей конкретного языка: читаем человеком и удобен для математического анализа. В курсе используются соглашения CLRS (Cormen et al.), в том числе:

Переменные (Variables): присваивание := (например, x := 5)
Массивы (Arrays): по умолчанию индексация с 1 (например, A[1] — первый элемент)
Циклы (Loops): for i = 1 to n (включительно), while condition
Отступы (Indentation): структура блоков как в Python
Комментарии (Comments): обычно // comment или отдельные блоки

1.3.3 Размер входа и время работы

Время \(T(n)\) обычно выражают через один параметр размера \(n\), иногда нужно несколько (например, \(T(n, k)\)).

Важная тонкость: время может зависеть не только от размера входа, но и от его структуры. Например, инкремент десятичного числа:

8456103473641089382376460123862354289341286512300012 — меняется одна цифра.
8456103473641089382379999999999999999999999999999999 — нужно обновить 32 цифры.

Оба входа одного размера (число цифр), но время разное. Поэтому анализируют разные случаи.

1.3.4 Лучший, средний и худший случай

Нужно выбрать, какие входы рассматривать:

Best case — вход, на котором алгоритм работает быстрее всего. Часто малоинформативен.
Average case — ожидаемое время по распределению входов. Практично, но сложнее анализировать.
Worst case — вход, на котором алгоритм работает дольше всего. Это дефолтный выбор: даёт гарантированную верхнюю оценку времени.

1.3.5 Как «считать» время работы

Оценивают вклад каждой инструкции через:

стоимость выполнения (Execution cost) одного выполнения;
частоту (Frequency count) — сколько раз инструкция выполняется.

Затем суммируют вклады.

1.3.6 Модель RAM

Для теоретического анализа используют RAM (Random-Access Machine):

Инструкции выполняются последовательно (без параллелизма).
Каждая базовая операция (\(+, -, \times, \div, :=, \le\), и т.д.) стоит 1 условную единицу времени.
Циклы и вызовы подпрограмм — не «базовые»: их стоимость зависит от числа выполнений.
Каждое обращение к памяти (чтение/запись) стоит 1 единицу.

В этой модели обычно анализируют worst-case time complexity.

1.3.7 Анализ сортировки вставками (Insertion Sort)

Insertion Sort — простой алгоритм сортировки «как карты в руке»: поддерживается отсортированный префикс, новый элемент вставляется на правильную позицию сдвигами вправо.

Псевдокод:

INSERTION-SORT(A, n)
1   for i = 2 to n
2       key = A[i]
3       j = i - 1
4       while j > 0 and A[j] > key
5           A[j + 1] = A[j]
6           j = j - 1
7       A[j + 1] = key

Как это работает:

Поддерживается отсортированный подмассив A[1…i-1]
На каждой итерации берётся A[i] и вставляется в отсортированную часть
Большие элементы сдвигаются на одну позицию вправо

Пример: сортировка [5, 2, 4, 6, 1, 3]

Старт: [5 | 2, 4, 6, 1, 3] (sorted | unsorted)
i=2: [2, 5 | 4, 6, 1, 3]
i=3: [2, 4, 5 | 6, 1, 3]
i=4: [2, 4, 5, 6 | 1, 3]
i=5: [1, 2, 4, 5, 6 | 3]
i=6: [1, 2, 3, 4, 5, 6 | ]

Анализ времени (worst case, обратный порядок):

Строка	Стоимость	Число выполнений	Вклад
1	\(c_1\)	\(n\)	\(c_1 n\)
2	\(c_2\)	\(n-1\)	\(c_2(n-1)\)
3	\(c_3\)	\(n-1\)	\(c_3(n-1)\)
4	\(c_4\)	\(\sum_{i=2}^{n} t_i\)	\(c_4 \sum_{i=2}^{n} t_i\)
5	\(c_5\)	\(\sum_{i=2}^{n} (t_i - 1)\)	\(c_5 \sum_{i=2}^{n} (t_i - 1)\)
6	\(c_6\)	\(\sum_{i=2}^{n} (t_i - 1)\)	\(c_6 \sum_{i=2}^{n} (t_i - 1)\)
7	\(c_7\)	\(n-1\)	\(c_7(n-1)\)

где \(t_i\) — число проверок условия while для данного \(i\).

В худшем случае (массив в обратном порядке) \(t_i = i\). Тогда: \[\sum_{i=2}^{n} t_i = \sum_{i=2}^{n} i = \frac{n(n+1)}{2} - 1\]

Суммарно получается \(T(n)\) вида \(an^2 + bn + c\), то есть \(\Theta(n^2)\) в худшем случае.

Ключевой вывод: внутренний while может выполниться до \(i-1\) раз для каждого \(i\), а \(\sum_{i=2}^{n}(i-1) = \frac{n(n-1)}{2} = \Theta(n^2)\).

1.4 Асимптотическая нотация

Точные формулы для \(T(n)\) громоздки; важнее порядок роста (order of growth) — как ведёт себя \(T(n)\) при больших \(n\).

Зачем это нужно? Сравним два алгоритма:

A: \(T_A(n) = 1000n\)
B: \(T_B(n) = n^2\)

При малых \(n\) (например, \(n=10\)) A «дороже», но при больших (\(n=10000\)) квадратичный рост B доминирует: константа перестаёт спасать.

Асимптотическая нотация описывает рост, игнорируя младшие члены и константные множители (в пределе больших \(n\)).

1.4.1 \(O\)-нотация (Big-O) — верхняя оценка

\(O(g(n))\) — множество функций, которые растут не быстрее \(g(n)\) с точностью до константы: \[O(g(n)) = \{f(n) \mid \exists\, c > 0,\, n_0 > 0 \text{ such that } \forall\, n \ge n_0: 0 \le f(n) \le c \cdot g(n)\}\]

На пальцах: \(f(n) = O(g(n))\) значит «\(f\) растёт не быстрее \(g\)» — существуют \(c\) и порог \(n_0\), после которого \(f(n) \le c\cdot g(n)\).

Как доказать \(f(n) = O(g(n))\): формулируем определение, подбираем \(c\) и \(n_0\), проверяем неравенство.

Пример: \(4n^2 + 100n + 500 = O(n^2)\).

Делим на \(n^2\): нужно \(4 + \frac{100}{n} + \frac{500}{n^2} \le c\). При \(n_0 = 1\) левая часть \(\le 604\), значит \(c=604\) подходит. При \(n_0=100\) можно взять меньшее \(c\).

Как доказать \(f(n) \ne O(g(n))\): показать, что для любых \(c, n_0\) найдётся \(n \ge n_0\) с \(f(n) > c\cdot g(n)\).

Пример: \(n^3 - 100n^2 \ne O(n^2)\): для больших \(n\) отношение к \(n^2\) растёт линейно по \(n\).

1.4.2 \(\Omega\)-нотация (Big-Omega) — нижняя оценка

\(\Omega(g(n))\) — функции, растущие не медленнее \(g(n)\): \[\Omega(g(n)) = \{f(n) \mid \exists\, c > 0,\, n_0 > 0 \text{ such that } \forall\, n \ge n_0: 0 \le c \cdot g(n) \le f(n)\}\]

Смысл: \(f(n) = \Omega(g(n))\) — «\(f\) не растёт медленнее \(g\)».

Отличие от Big-O: \(O\) — «потолок», \(\Omega\) — «пол».

1.4.3 \(\Theta\)-нотация (Theta) — тесная оценка

\(\Theta(g(n))\) — функции того же порядка, что и \(g(n)\): \[\Theta(g(n)) = \{f(n) \mid \exists\, c_1, c_2, n_0 > 0 \text{ such that } \forall\, n \ge n_0: 0 \le c_1 g(n) \le f(n) \le c_2 g(n)\}\]

Теорема 3.1: \(f(n) = \Theta(g(n))\) тогда и только тогда, когда \(f(n) = O(g(n))\) и \(f(n) = \Omega(g(n))\).

1.4.4 \(o\)-нотация (Little-o) — строго «медленнее»

\[o(g(n)) = \{f(n) \mid \forall\, c > 0,\, \exists\, n_0 > 0 \text{ such that } \forall\, n \ge n_0: 0 \le f(n) < c \cdot g(n)\}\]

Отличие от Big-O: в \(O\) константу \(c\) мы выбираем сами; в \(o\) условие должно выполняться для всех \(c>0\) (даже сколь угодно малых).

Через предел: \(f(n) = o(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0\).

1.4.5 \(\omega\)-нотация (Little-omega) — строго «быстрее»

\[\omega(g(n)) = \{f(n) \mid \forall\, c > 0,\, \exists\, n_0 > 0 \text{ such that } \forall\, n \ge n_0: 0 \le c \cdot g(n) < f(n)\}\]

Через предел: \(f(n) = \omega(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty\).

Связь: \(f(n) = o(g(n)) \iff g(n) = \omega(f(n))\).

Сводка пяти нотаций:

Нотация	Смысл	Аналогия	Предел
\(f = O(g)\)	\(f\) растёт не быстрее \(g\)	\(\le\)	\(\limsup \frac{f}{g} < \infty\)
\(f = \Omega(g)\)	\(f\) растёт не медленнее \(g\)	\(\ge\)	\(\liminf \frac{f}{g} > 0\)
\(f = \Theta(g)\)	\(f\) того же порядка роста, что и \(g\)	\(=\)	\(0 < \lim \frac{f}{g} < \infty\)
\(f = o(g)\)	\(f\) растёт строго медленнее \(g\)	\(<\)	\(\lim \frac{f}{g} = 0\)
\(f = \omega(g)\)	\(f\) растёт строго быстрее \(g\)	\(>\)	\(\lim \frac{f}{g} = \infty\)

1.4.6 Корректное использование асимптотики

«В худшем случае время работы insertion sort — \(O(n^2)\)» — верно (верхняя оценка худшего случая).
«В худшем случае … \(\Omega(n^2)\)» — верно (нижняя оценка худшего случая).
«В худшем случае … \(\Theta(n^2)\)» — верно (тесная оценка худшего случая).
«Время работы insertion sort — \(\Theta(n^2)\)» — неверно без уточнения случая (в лучшем случае \(\Theta(n)\)).
«Алгоритм работает как минимум \(O(n^2)\)» — плохая терминология: \(O\) — верхняя оценка; для «как минимум» используйте \(\Omega\).

1.4.7 Асимптотика внутри формул

Например, \(2n^2 + 3n + 1 = 2n^2 + \Theta(n)\) означает: существует \(f(n)=\Theta(n)\), что равенство выполняется. В цепочках равенств каждое равенство понимается отдельно.

1.5 Свойства асимптотической нотации

Рефлексивность: \(f(n)=\Theta(f(n))\), \(f(n)=O(f(n))\), \(f(n)=\Omega(f(n))\).
Транзитивность: если \(f=\Theta(g)\) и \(g=\Theta(h)\), то \(f=\Theta(h)\) (аналогично для \(O,\Omega,o,\omega\)).
Симметрия \(\Theta\): \(f=\Theta(g) \iff g=\Theta(f)\).
Transpose symmetry: \(f=O(g) \iff g=\Omega(f)\); \(f=o(g) \iff g=\omega(f)\).
Нет трихотомии: возможны колебания, когда ни \(o\), ни \(\Theta\), ни \(\omega\) не выполняется (пример: \(f(n)=n^{1+\sin n}\)).

1.6 Типовые функции и рост

1.6.1 Многочлены

Старший член доминирует: если \(a_d>0\), то \(p(n)=\Theta(n^d)\).

1.6.2 Экспоненты

Для любых констант \(a>1\) и \(b\): \(n^b = o(a^n)\) — экспонента быстрее любого многочлена.

1.6.3 Логарифмы

\(\log^b n = o(n^a)\) для любого \(a>0\). Здесь \(\log^b n = (\log n)^b\).

База логарифма не важна асимптотически: \(\log_2 n = \Theta(\ln n)\).

1.6.4 Факториалы

\(n! \le n^n\), \(n! \ge (n/2)^{n/2}\), формула Стирлинга: \[n! = \sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(1 + \Theta\left(\frac{1}{n}\right)\right)\] и \(\log(n!) = \Theta(n\log n)\).

Иерархия роста (очень грубо): \[1 \prec \log\log n \prec \log n \prec (\log n)^2 \prec \sqrt{n} \prec n \prec n\log n \prec n^2 \prec n^3 \prec 2^n \prec n! \prec n^n\]

Практическая интерпретация:

Constant (\(1\)): наилучший случай — время не растёт с размером входа.
Logarithmic (\(\log n\)): очень благоприятно — типично у divide-and-conquer, когда задача каждый раз делится константным образом.
Linear (\(n\)): хорошо — в большинстве задач нужно хотя бы «просмотреть» каждый элемент входа.
Linearithmic (\(n \log n\)): хорошо — для comparison-based sorting это оптимальный порядок.
Quadratic (\(n^2\)): на малых \(n\) часто приемлемо; на больших входах квадратичный рост без веской причины обычно уже неприемлем.
Cubic (\(n^3\)) и выше: оправданы только при гарантированно малом \(n\).
Exponential (\(2^n\), \(n!\), \(n^n\)): на умеренных \(n\) (часто уже \(n>30\)) на практике становится intractable — вычислительно неподъёмно.

2. Определения

Algorithm: чётко определённая вычислительная процедура: конечное время, вход → выход; последовательность шагов преобразования входа в выход.
Computational problem: спецификация желаемой связи вход/выход для всех допустимых экземпляров.
Correct algorithm: для каждого допустимого входа завершается за конечное время и выдаёт корректный выход по определению задачи.
Loop invariant: свойство в терминах переменных цикла, истинное до/после каждой итерации; используется для доказательств через initialization, maintenance, termination.
Algorithm analysis: как растут требования к ресурсам (время, память) с размером входа; часто worst-case.
Time complexity: как время работы растёт как функция размера входа; обычно в асимптотике.
Space complexity: сколько дополнительной памяти нужно как функция размера входа.
Input size: мера объёма входных данных (число элементов, длина строки, число бит, размерность матрицы).
Running time \(T(n)\): число примитивных операций как функция размера входа \(n\).
Best-case / Average-case / Worst-case analysis: анализ на самом быстром входе / в среднем / на самом медленном входе.
RAM model (Random-Access Machine): последовательные инструкции; базовые операции и доступ к памяти за 1 единицу.
Execution cost и Frequency count: стоимость одного выполнения инструкции и число выполнений.
Asymptotic notation: \(O,\Omega,\Theta,o,\omega\) для порядка роста при \(n\to\infty\).
Order of growth: «форма» роста, обычно по доминирующему члену.
Big-O / Big-Omega / Theta / little-o / little-omega: как в разделе 1.4 (формальные определения сохраняются).
Pseudocode: полуформальное высокоуровневое описание алгоритма для анализа и читаемости.

3. Формулы

\(O\)-notation: \(O(g(n)) = \{f(n) \mid \exists\, c, n_0 > 0.\ \forall\, n \ge n_0:\ 0 \le f(n) \le c \cdot g(n)\}\)
\(\Omega\)-notation: \(\Omega(g(n)) = \{f(n) \mid \exists\, c, n_0 > 0.\ \forall\, n \ge n_0:\ 0 \le c \cdot g(n) \le f(n)\}\)
\(\Theta\)-notation: \(\Theta(g(n)) = \{f(n) \mid \exists\, c_1, c_2, n_0 > 0.\ \forall\, n \ge n_0:\ 0 \le c_1 g(n) \le f(n) \le c_2 g(n)\}\)
\(o\)-notation: \(o(g(n)) = \{f(n) \mid \forall\, c > 0.\ \exists\, n_0 > 0.\ \forall\, n \ge n_0:\ 0 \le f(n) < c \cdot g(n)\}\)
\(\omega\)-notation: \(\omega(g(n)) = \{f(n) \mid \forall\, c > 0.\ \exists\, n_0 > 0.\ \forall\, n \ge n_0:\ 0 \le c \cdot g(n) < f(n)\}\)
Theorem 3.1 (\(\Theta\) decomposition): \(f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \text{ and } f(n) = \Omega(g(n))\)
Transpose symmetry: \(f(n) = O(g(n)) \iff g(n) = \Omega(f(n))\); \(f(n) = o(g(n)) \iff g(n) = \omega(f(n))\)
Polynomial growth: если \(p(n) = a_d n^d + \dots + a_0\) и \(a_d > 0\), то \(p(n) = \Theta(n^d)\)
Exponential dominates polynomial: \(n^b = o(a^n)\) при \(a > 1\)
Polynomial dominates polylogarithm: \(\log^b n = o(n^a)\) при \(a > 0\)
Stirling’s approximation: \(n! = \sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(1 + \Theta\left(\frac{1}{n}\right)\right)\)
Factorial bounds: \(n! = o(n^n)\), \(n! = \omega(2^n)\), \(\log(n!) = \Theta(n \log n)\)
Little-o via limit: \(f(n) = o(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0\)
Little-omega via limit: \(f(n) = \omega(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty\)

4. Примеры

4.1. Доказать корректность и оценить exp1 (Лаба 1, Задание 1)

Докажите корректность следующего алгоритма возведения в степень и оцените time complexity:

function exp1(a, n)
begin
  k := n
  b := 1
  while k != 0 do
  begin
    k := k - 1
    b := b * a
  end
  return b
end

Нажмите, чтобы увидеть решение

Ключевая идея: инвариант цикла, затем подсчёт итераций.

Инвариант: \(b \cdot a^k = a^n\) до и после каждой итерации.

Initialization: до первой итерации \(k=n\), \(b=1\), значит \(b\cdot a^k=a^n\). ✓

Maintenance: пусть перед итерацией \(b\cdot a^k=a^n\). После тела: \(k'=k-1\), \(b'=b\cdot a\). Тогда \(b'\cdot a^{k'}=(b\cdot a)\cdot a^{k-1}=b\cdot a^k=a^n\). ✓

Termination: при \(k=0\) получаем \(b=a^n\). ✓
Time complexity: цикл выполняется \(n\) раз; внутри \(O(1)\) операций (при модели, где умножения «помещаются» в \(O(1)\)). Итого \(T(n)=\Theta(n)\).

Ответ: корректность через инвариант; время \(\Theta(n)\).

4.2. Доказать корректность и оценить exp2 (Лаба 1, Задание 2)

Докажите корректность быстрого возведения в степень и оцените time complexity:

function exp2(a, n)
begin
  k := n
  b := 1
  c := a
  while k != 0 do
    if k mod 2 = 0 then
      k := k / 2
      c := c * c
    else
      k := k - 1
      b := b * c
  return b
end

Нажмите, чтобы увидеть решение

Ключевая идея: binary exponentiation; инвариант \(b\cdot c^k=a^n\).

Инвариант: \(b\cdot c^k=a^n\) до и после каждой итерации.

Initialization: \(b=1,c=a,k=n\) ⇒ \(b\cdot c^k=a^n\). ✓

Maintenance: пусть \(b \cdot c^k = a^n\).
- Если \(k\) чётно: \(k' = k/2\), \(c' = c^2\). Тогда \(b' \cdot c'^{k'} = b \cdot (c^2)^{k/2} = b \cdot c^k = a^n\). ✓
- Если \(k\) нечётно: \(k' = k - 1\), \(b' = b \cdot c\). Тогда \(b' \cdot c'^{k'} = (b \cdot c) \cdot c^{k-1} = b \cdot c^k = a^n\). ✓
Termination: при \(k=0\) получаем \(b=a^n\). ✓
Time complexity: \(k\) убывает экспоненциально быстро (деление на 2 / редкий декремент), итого \(\Theta(\log n)\).

Ответ: корректность через инвариант; время \(\Theta(\log n)\).

4.3. Наивный GCD (Лаба 1, Задание 3)

Докажите корректность и оцените time complexity:

function gcd1(a, b)
begin
  if a > b then
    k := a
  else
    k := b
  while (a mod k != 0) or (b mod k != 0) do
    k := k - 1
  return k
end

Нажмите, чтобы увидеть решение

Ключевая идея: перебор \(k\) сверху вниз до первого общего делителя — по определению это \(\gcd(a,b)\).

Корректность: \(\gcd\) — наибольший общий делитель; алгоритм находит первый \(k\) сверху, делящий оба числа.

Time complexity: в худшем случае \(\Theta(\max(a,b))\) итераций с модулем ⇒ \(\Theta(m)\) для \(m=\max(a,b)\).

Ответ: корректность по определению \(\gcd\); время \(\Theta(\max(a,b))\).

4.4. Евклидов gcd2 (Лаба 1, Задание 4)

Докажите корректность и оцените time complexity:

function gcd2(a, b)
begin
  m := a
  n := b
  while (m != 0) and (n != 0) do
    if m >= n then
      m := m - n
    else
      n := n - m
  return (n + m)
end

Нажмите, чтобы увидеть решение

Ключевая идея: инвариант \(\gcd(m,n)=\gcd(a,b)\); версия с вычитаниями.

Корректность: классическое свойство \(\gcd(x,y)=\gcd(x-y,y)\) сохраняет \(\gcd\); на выходе один ноль.

Time complexity: при показанных повторных вычитаниях число шагов может быть велико; у классического варианта Евклида с делением число итераций обычно записывают как \(O(\log(\min(a,b)))\).

Ответ: корректность через инвариант; для делительного варианта \(O(\log(\min(a,b)))\).

4.5. Вычислить worst-case time complexity в \(\Theta\)-нотации (Набор задач 1, Задание 1)

Вычислите временную сложность в худшем случае в асимптотике (worst-case time complexity) следующего алгоритма (соглашения псевдокода см. в CLRS, §2.1). Используйте \(\Theta\)-нотацию. Дайте полное обоснование: execution cost и frequency count для каждой строки и детали вычисления \(T(n)\) в worst case.

/* A is a 1-indexed array,
 * n is the number of items in A */
function secret(A, n)
    r := n
    while (2 * r > n)
        k := n - r + 1
        i := r
        for j = k to r
            if (A[j] < A[i])
                i := j
            if (A[j] > A[k])
                k := j
        exchange A[i] with A[r]
        exchange A[k] with A[n - r + 1]
        r := r - 1

Нажмите, чтобы увидеть решение

Ключевая идея: для каждой строки оцениваем стоимость и частоту, затем суммируем вклады в \(T(n)\).

1. Сколько раз выполняется внешний while.

Переменная \(r\) стартует с \(n\) и уменьшается на 1 за итерацию. Цикл выполняется при \(2r > n\), т.е. \(r > n/2\). Значит \(r\) идёт от \(n\) вниз примерно до \(\lceil n/2 \rceil + 1\), что даёт порядка \(\lfloor n/2 \rfloor\) итераций внешнего цикла.

2. Сколько раз выполняется for на одну внешнюю итерацию.

В каждой внешней итерации \(k = n - r + 1\), а for идёт от \(j=k\) до \(j=r\). Число итераций: \[r - k + 1 = r - (n - r + 1) + 1 = 2r - n.\]

При \(r=n\): внутренний цикл выполняется \(2n-n=n\) раз. При \(r=\lceil n/2\rceil+1\): получается около \(2\) раз.

3. Таблица cost / frequency (worst case).

Строка	Код	Стоимость	Частота (худший случай)
4	`r := n`	\(c_4\)	\(1\)
5	`while (2 * r > n)`	\(c_5\)	\(\lfloor n/2 \rfloor + 1\)
6	`k := n - r + 1`	\(c_6\)	\(\lfloor n/2 \rfloor\)
7	`i := r`	\(c_7\)	\(\lfloor n/2 \rfloor\)
8	`for j = k to r`	\(c_8\)	\(\sum_{r=\lceil n/2\rceil+1}^{n}(2r - n + 1)\)
9	`if (A[j] < A[i])`	\(c_9\)	\(\sum_{r=\lceil n/2\rceil+1}^{n}(2r - n)\)
10	`i := j`	\(c_{10}\)	\(\sum_{r=\lceil n/2\rceil+1}^{n}(2r - n)\) (worst case)
11	`if (A[j] > A[k])`	\(c_{11}\)	\(\sum_{r=\lceil n/2\rceil+1}^{n}(2r - n)\)
12	`k := j`	\(c_{12}\)	\(\sum_{r=\lceil n/2\rceil+1}^{n}(2r - n)\) (worst case)
13	`exchange A[i] with A[r]`	\(c_{13}\)	\(\lfloor n/2 \rfloor\)
14	`exchange A[k] with A[n-r+1]`	\(c_{14}\)	\(\lfloor n/2 \rfloor\)
15	`r := r - 1`	\(c_{15}\)	\(\lfloor n/2 \rfloor\)

4. Внутренняя сумма.

\[\sum_{r=\lceil n/2\rceil+1}^{n}(2r - n) = \sum_{m=1}^{\lfloor n/2 \rfloor} 2m \quad \text{(подстановка } m = r - \lceil n/2 \rceil\text{)}\]

Корректно: при \(r\) от \(\lceil n/2\rceil+1\) до \(n\) величина \(2r-n\) даёт вклад порядка \(\Theta(n^2)\); точнее, сумма \(\Theta\left(\lfloor n/2\rfloor(\lfloor n/2\rfloor+1)\right)=\Theta(n^2)\).

5. Итоговое \(T(n)\).

\[T(n) = \Theta(1) + \Theta(n) + \Theta(n^2) = \Theta(n^2)\]

Ответ: \(T(n) = \Theta(n^2)\)

4.6. Инвариант цикла для алгоритма reorder (Набор задач 1, Задание 2)

Следующий алгоритм переставляет элементы входного массива. Например:

Вход: [2, 1, 4, 3, 5, 8, 9] \(\Longrightarrow\) Выход: [2, 4, 5, 8, 9, 3, 1]

/* A is a 1-indexed array,
 * n is the number of items in A */
function reorder(A, n)
    k := 0
    for i = 1 to (n - 1)
        if A[i - k] < A[i + 1]
            exchange A[i - k + 1] with A[i + 1]
        else:
            k := k + 1

Пусть \(n > 0\). Верно ли, что элемент с индексом \((n - k)\) в выходном массиве всегда равен максимальному элементу входного массива? Если да — докажите через loop invariant. Если нет — приведите counterexample.

Нажмите, чтобы увидеть решение

Ключевая идея: понять поведение алгоритма и проверить утверждение на примерах, затем дать инвариант.

1. Трассировка примера.

Вход: \(A = [2, 1, 4, 3, 5, 8, 9]\), \(n = 7\).

\(i=1, k=0\): \(A[1]=2 < A[2]=1\)? Нет. \(k=1\).
\(i=2, k=1\): \(A[1]=2 < A[3]=4\)? Да. Обмен \(A[2]\) и \(A[3]\): \([2, 4, 1, 3, 5, 8, 9]\).
\(i=3, k=1\): \(A[2]=4 < A[4]=3\)? Нет. \(k=2\).
\(i=4, k=2\): сравниваем \(A[4-2]=A[2]=4\) с \(A[5]=5\). \(4 < 5\)? Да. Обмен \(A[4-2+1]=A[3]=1\) с \(A[5]=5\). Массив: \([2, 4, 5, 3, 1, 8, 9]\).
\(i=5\): сравниваем \(A[5-2]=A[3]=5\) с \(A[6]=8\). \(5 < 8\)? Да. Обмен \(A[5-2+1]=A[4]=3\) с \(A[6]=8\). Массив: \([2, 4, 5, 8, 1, 3, 9]\).
\(i=6\): сравниваем \(A[6-2]=A[4]=8\) с \(A[7]=9\). \(8 < 9\)? Да. Обмен \(A[6-2+1]=A[5]=1\) с \(A[7]=9\). Массив: \([2, 4, 5, 8, 9, 3, 1]\).

Выход: \([2, 4, 5, 8, 9, 3, 1]\), \(k = 2\). Индекс \(n - k = 7 - 2 = 5\). \(A[5] = 9\) — действительно максимум.

2. Дополнительные примеры. Во всех рассмотренных входах индекс \(n-k\) указывает на максимум.

3. Доказательство инвариантом.

Инвариант: после итерации \(i\) элемент \(A[i - k + 1]\) — максимум среди \(\{A[1], \dots, A[i+1]\}\) (в смысле эволюции массива), и он находится в позиции \(i - k + 1\).

Точнее: в конце каждой итерации \(A[i+1-k]\) равен максимуму среди первых \(i+1\) элементов исходного массива.

Initialization (\(i=0\), до цикла): \(k=0\), префикс из одного элемента \(\{A[1]\}\), максимум — \(A[1]\) на индексе \(1 = 1-0+0\).

Maintenance: предположим, что после итерации \(i-1\) максимум \(\{A[1],\dots,A[i]\}\) стоит в индексе \(i-k\). На итерации \(i\):

Сравниваем \(A[i-k]\) (текущий максимум) с \(A[i+1]\).
Случай 1: \(A[i-k] < A[i+1]\): новый максимум — \(A[i+1]\). Обмен \(A[i-k+1]\) с \(A[i+1]\) переносит максимум в позицию \(i-k+1=(i+1)-k\).
Случай 2: \(A[i-k] \ge A[i+1]\): максимум остаётся \(A[i-k]\). Увеличиваем \(k\), тогда максимум оказывается в индексе \(i-k = (i+1)-(k+1)\).

Termination: при \(i=n\) получаем, что максимум всего \(\{A[1],\dots,A[n]\}\) находится в индексе \(n-k\).

Ответ: да, утверждение верно: элемент с индексом \((n-k)\) в выходе всегда совпадает с максимумом входа.

4.7. Асимптотика: TRUE или FALSE (Набор задач 1, Задание 3)

Для каждого утверждения определите TRUE или FALSE. Дайте полное обоснование через формальные определения и/или известные свойства асимптотической нотации.

Верно ли, что \(n^4 - 20n^2 - 1 = \Theta(n^4)\)?
Верно ли, что \(\log_2(\log_3 n) = O(\log_6 n)\)?
Верно ли, что \(\min(\log n, \sqrt{n}) = \Omega(\log n + \sqrt{n})\)?
Верно ли, что \(n 2^n = o(3^n)\)?
Верно ли, что \((n - 1)! = \Theta(n!)\)?

Нажмите, чтобы увидеть решение

(1) \(n^4 - 20n^2 - 1 = \Theta(n^4)\)?

TRUE.

По «правилу многочленов» многочлен степени \(d\) с положительным старшим коэффициентом есть \(\Theta(n^d)\). Здесь \(f(n)=n^4-20n^2-1\) — многочлен степени 4 со старшим коэффициентом 1.

Формально:

\(O\): \(n^4-20n^2-1 \le n^4\). Берём \(c_2=1\), \(n_0=1\).
\(\Omega\): для \(n\ge 7\) можно показать \(f(n)\ge n^4/2\). Берём \(c_1=1/2\), \(n_0=7\).

По Theorem 3.1, \(f(n)=\Theta(n^4)\).

(2) \(\log_2(\log_3 n) = O(\log_6 n)\)?

TRUE.

Имеем \(\log_3 n=\Theta(\ln n)\) и \(\log_6 n=\Theta(\ln n)\), а \(\log_2(\log_3 n)=\Theta(\log\log n)\). Поскольку \(\log\log n=o(\log n)\), следует \(\log_2(\log_3 n)=O(\log_6 n)\).

(3) \(\min(\log n, \sqrt{n}) = \Omega(\log n + \sqrt{n})\)?

FALSE.

Для больших \(n\) выполнено \(\log n=o(\sqrt{n})\), значит \(\min(\log n,\sqrt{n})=\log n\). Но \(\log n+\sqrt{n}\ge \sqrt{n}\), и отношение \(\log n/(\log n+\sqrt{n})\) не удерживается снизу положительной константой, потому что \(\log n=o(\sqrt{n})\).

(4) \(n2^n=o(3^n)\)?

TRUE.

\[\lim_{n\to\infty}\frac{n2^n}{3^n}=\lim_{n\to\infty} n(2/3)^n=0.\]

(5) \((n-1)!=\Theta(n!)\)?

FALSE.

\(n!=n\cdot(n-1)!\), поэтому \((n-1)!/n!=1/n\to 0\), т.е. \((n-1)!=o(n!)\), откуда \((n-1)!\ne \Theta(n!)\).

Ответ: (1) TRUE, (2) TRUE, (3) FALSE, (4) TRUE, (5) FALSE.

4.8. Проверка алгоритма `exp` на примерах (Лекция 1, Пример 1)

Что вычисляет алгоритм exp(a, n) на входах:

\(a = 2, n = 3\)
\(a = 3, n = 2\)

function exp(a, n)
begin
    k := 0
    b := 1
    while k != n do
    begin
        k := k + 1
        b := b * a
    end
    return b
end

Нажмите, чтобы увидеть решение

Ключевая идея: пошаговая трассировка.

(a) \(a = 2, n = 3\):

Итерация	\(k\) (до)	\(b\) (до)	\(k\) (после)	\(b\) (после)
1	0	1	1	\(1 \times 2 = 2\)
2	1	2	2	\(2 \times 2 = 4\)
3	2	4	3	\(4 \times 2 = 8\)

Теперь \(k = 3 = n\), цикл заканчивается. Возвращаем \(b = 8 = 2^3\).

(b) \(a = 3, n = 2\):

Итерация	\(k\) (до)	\(b\) (до)	\(k\) (после)	\(b\) (после)
1	0	1	1	\(1 \times 3 = 3\)
2	1	3	2	\(3 \times 3 = 9\)

Теперь \(k = 2 = n\), цикл заканчивается. Возвращаем \(b = 9 = 3^2\).

Ответ: (a) \(8\), (b) \(9\).

4.9. Доказать \(2^{n+1} = O(2^n)\) (Лекция 1, Задание 1)

Верно ли, что \(2^{n+1} = O(2^n)\)? Если да — докажите.

Нажмите, чтобы увидеть решение

Ключевая идея: \(2^{n+1}=2\cdot 2^n\).

Да.

Нужны \(c,n_0>0\): \(0\le 2\cdot 2^n \le c\cdot 2^n\) для всех \(n\ge n_0\). Берём \(c=2\), \(n_0=1\).

Ответ: да; \(2^{n+1}=O(2^n)\) с \(c=2\), \(n_0=1\).

4.10. Доказать \(2^{2n} \ne O(2^n)\) (Лекция 1, Задание 2)

Верно ли, что \(2^{2n} = O(2^n)\)? Если да — докажите; если нет — опровергните.

Нажмите, чтобы увидеть решение

Ключевая идея: \(2^{2n}=(2^n)^2=4^n\).

Нет.

Если бы \(4^n\le c2^n\), то \(2^n\le c\) для всех больших \(n\), что невозможно.

Ответ: нет; \(2^{2n}\ne O(2^n)\).

4.11. Доказать \(\max(f(n), g(n)) = \Theta(f(n) + g(n))\) (Лекция 1, Задание 3)

Докажите, что \(\max(f(n), g(n)) = \Theta(f(n) + g(n))\), предполагая \(f(n)\ge 0\) и \(g(n)\ge 0\) для всех \(n\).

Нажмите, чтобы увидеть решение

Ключевая идея: две оценки и Theorem 3.1.

\(O\): \(\max(f,g)\le f+g\), значит \(\max(f,g)=O(f+g)\) с \(c_2=1\), \(n_0=1\).

\(\Omega\): \(2\max(f,g)\ge f+g\), значит \(\max(f,g)\ge \tfrac12(f+g)\), т.е. \(\Omega(f+g)\) с \(c_1=1/2\), \(n_0=1\).

Ответ: доказано с \(c_1=1/2\), \(c_2=1\), \(n_0=1\).

4.12. Доказать \((n + a)^b = \Theta(n^b)\) (Лекция 1, Задание 4)

Докажите, что \((n + a)^b = \Theta(n^b)\) для любой константы \(a\) и любой положительной константы \(b\).

Нажмите, чтобы увидеть решение

Ключевая идея: для больших \(n\) слагаемое \(a\) мало относительно \(n\).

\(O\): при \(n\ge |a|\) имеем \(n+a\le 2n\), откуда \((n+a)^b\le 2^b n^b\). Берём \(c_2=2^b\), \(n_0=|a|\).

\(\Omega\): при \(n\ge 2|a|\) имеем \(n+a\ge n/2\), откуда \((n+a)^b\ge n^b/2^b\). Берём \(c_1=1/2^b\), \(n_0=2|a|\).

Ответ: доказано с \(c_1=1/2^b\), \(c_2=2^b\), \(n_0=2|a|\).

4.13. Правило произведения для \(O\)-notation (Лекция 1, Задание 5)

Докажите: если \(f(n)=O(n^2)\) и \(g(n)=O(\log n)\), то \(f(n)\cdot g(n)=O(n^2\log n)\).

Нажмите, чтобы увидеть решение

Ключевая идея: перемножить верхние оценки.

Из условий существуют \(c_1,n_1\) и \(c_2,n_2\). Для \(n\ge n_0=\max(n_1,n_2)\): \[0\le f(n)g(n)\le c_1c_2\, n^2\log n.\]

Ответ: \(c=c_1c_2\), \(n_0=\max(n_1,n_2)\).

4.14. Из \(k \ln k = \Theta(n)\) следует \(k = \Theta(n / \ln n)\) (Лекция 1, Задание 6)

Докажите: если \(k\ln k=\Theta(n)\), то \(k=\Theta(n/\ln n)\).

Нажмите, чтобы увидеть решение

Ключевая идея: оценить \(k\) и \(\ln k\) через \(n\), затем «перенести» \(\Theta\).

Из \(k\ln k=\Theta(n)\) получаем двусторонние неравенства \(c_1 n\le k\ln k\le c_2 n\), далее показывают \(\ln k=\Theta(\ln n)\) и выводят \[k=\frac{\Theta(n)}{\ln k}=\Theta\!\left(\frac{n}{\ln n}\right).\]

Ответ: \(k=\Theta(n/\ln n)\).

1. Краткое содержание

1.1 Что такое алгоритм?

1.1.1 Вычислительные задачи

1.2 Корректность алгоритма

1.2.1 Подходы к доказательству корректности

1.2.2 Инварианты цикла (Loop Invariants)

1.2.3 Пример инварианта цикла: возведение в степень

1.3 Анализ алгоритмов

1.3.1 Зачем анализировать алгоритмы?

1.3.2 Эмпирический и теоретический анализ

1.3.3 Размер входа и время работы

1.3.4 Лучший, средний и худший случай

1.3.5 Как «считать» время работы

1.3.6 Модель RAM

1.3.7 Анализ сортировки вставками (Insertion Sort)

1.4 Асимптотическая нотация

1.4.1 \(O\)-нотация (Big-O) — верхняя оценка

1.4.2 \(\Omega\)-нотация (Big-Omega) — нижняя оценка

1.4.3 \(\Theta\)-нотация (Theta) — тесная оценка

1.4.4 \(o\)-нотация (Little-o) — строго «медленнее»

1.4.5 \(\omega\)-нотация (Little-omega) — строго «быстрее»

1.4.6 Корректное использование асимптотики

1.4.7 Асимптотика внутри формул

1.5 Свойства асимптотической нотации

1.6 Типовые функции и рост

1.6.1 Многочлены

1.6.2 Экспоненты

1.6.3 Логарифмы

1.6.4 Факториалы

2. Определения

3. Формулы

4. Примеры

4.1. Доказать корректность и оценить exp1 (Лаба 1, Задание 1)

4.2. Доказать корректность и оценить exp2 (Лаба 1, Задание 2)

4.3. Наивный GCD (Лаба 1, Задание 3)

4.4. Евклидов gcd2 (Лаба 1, Задание 4)

4.5. Вычислить worst-case time complexity в \(\Theta\)-нотации (Набор задач 1, Задание 1)

4.6. Инвариант цикла для алгоритма reorder (Набор задач 1, Задание 2)

4.7. Асимптотика: TRUE или FALSE (Набор задач 1, Задание 3)

4.8. Проверка алгоритма exp на примерах (Лекция 1, Пример 1)

4.9. Доказать \(2^{n+1} = O(2^n)\) (Лекция 1, Задание 1)

4.10. Доказать \(2^{2n} \ne O(2^n)\) (Лекция 1, Задание 2)

4.11. Доказать \(\max(f(n), g(n)) = \Theta(f(n) + g(n))\) (Лекция 1, Задание 3)

4.12. Доказать \((n + a)^b = \Theta(n^b)\) (Лекция 1, Задание 4)

4.13. Правило произведения для \(O\)-notation (Лекция 1, Задание 5)

4.14. Из \(k \ln k = \Theta(n)\) следует \(k = \Theta(n / \ln n)\) (Лекция 1, Задание 6)

4.8. Проверка алгоритма `exp` на примерах (Лекция 1, Пример 1)